package lyl.binaryseach;

/**
 * n 跟木头，最终切成至少k根，求切成的最大长度
 * 数组给出每根木头的长度
 */
public class WoodCut {
    //L is a array with wood length
    //k is the pieces for asked
    //cut length is the longest wood ,1 ->length
    //summit all wood's pieces
    //keep the pieces smaller and the length higher
    public int woodCut(int[] L,int k){

        if(L == null || L.length == 0){
            return 0;
        }
        if(k <= 0){
            return 0;
        }
        int left = 1;
        int right = 0;
        for (int length : L) {
            if(right < length){
                right = length;
            }
        }
        while(left + 1 < right){
            int mid = left + (right - left)/2;
            if(count(L,mid) >= k){ //分的段数超过了要求的，说明可以切大一点
                left = mid;
            }else {
                right = mid;
            }
        }
        if(count(L,right)>=k){
            return right;
        }
        if(count(L,left)>=k){
            return left;
        }
        return 0;
    }

    //求总份数，mid为每段的长度
    private int count(int[] l, int mid) {
        int pieces = 0;
        for (int length : l) {
            pieces += length/mid;
        }
        return pieces;
    }
}
